codefandomcom-20200214-history
Linked list
A linked list is a list made up of nodes, each of which contains information and points to another node. Using recursion, a linked list can be created, searched from, sorted and deleted. There are many types of linked lists according to its structure: * singly-linked/doubly-linked list - In a doubly-linked list, each node points to the node after it and the node before it. In a singly-linked list, each node points only to the node after it. * linear (non-circular)/circular list - In a circular list, the last node points to the first node. * lists with sentinel nodes - Sentinel nodes are sometimes used to simplify the implementation of a linked list. These nodes can occur at the end of the list, and sometimes at the beginning, depending on the implementation. The linked structure allows data to be dynamically added and deleted in constant time, but it can only be accessed sequentially (that is, it does not allow random access). List/node structure A node is a data structure that contains some arbitrary information and also points to another node (this is usually done in the form of pointers). The information can be restricted to a specific type in generic lists. In linear lists, the last node in the list points to either a null reference or a sentinel node. This is also true for the first node in a doubly-linked list. Below is a declaration of a node in a linked list of integers in C: typedef struct n { int value; n* next; } node; Storage of a list In lower languages, a linked list is commonly accessed by a pointer to the first item in it (the "head") and, when needed, the last item in it (the "tail"). Creation of a list The creation of a list varies with the structure. Below is a common declaration of an empty singly-linked list in C: node* head, tail = NULL; Printing a list This involves outputting the contents of the list to the screen. The process is similar when outputting to an arbitrary string, stream or file. The idea is to iterate though each element in the list, but do not print at all if it is empty. Example in C: node* p = head; while(p != null) { print("%d ", p->value); p = p->next; } Adding an item This involves adding a pointer to the end of a linked list. The idea is making the last node point to the added item, then the item would now be the last node. Example in C: int n; // assign a value to n node* new = newnode(n); if(tail null) { *tail = new; } else { tail->next = new; *tail = new; } newnode is basically allocating memory for the new node. node* newnode(int n) { node* rnode; rnode = (node*)malloc(sizeof(node)); rnode->next = null; rnode->value = n; return rnode; } See Also * Array * Stack * Queue * Map * Heap * Deque Category:Data structures